#include <iostream>
#include <string.h>

using namespace std;

typedef enum
{
    Link,
    Thread
} NodeTag;

class TreeNode
{
private:
    char data;            // 值
    TreeNode *leftChild;  // 左孩子
    TreeNode *rightChild; // 右孩子
    NodeTag lTag, rTag;   // 线索Tag

    friend class MyTree; // 树类
public:
    TreeNode(char, TreeNode *, TreeNode *, NodeTag, NodeTag);
    ~TreeNode();

    void printNode();
};

class MyTree
{
private:
    TreeNode *root; // 根指针
    bool isThread;  // 线索二叉树标志
public:
    MyTree();               // 无参构造
    MyTree(const char[]);   // 构造函数
    MyTree(const MyTree &); // 拷贝函数
    ~MyTree();              // 析构函数

    void preOrderTraverse();              // 前序遍历
    void inOrderTraverse();               // 中序遍历
    void postOrderTraverse();             // 后序遍历
    int countLeaf();                      // 叶结点计数
    int countHeight();                    // 计算树的深度
    bool isThreadedTree();                // 判断是否为线索二叉树
    bool inOrderThreading();              // 线索化
    TreeNode &locateNode(const char &);   // 结点定位
    TreeNode &preNode(const TreeNode &);  // 获取前驱结点
    TreeNode &nextNode(const TreeNode &); // 获取后继结点

    // add
    TreeNode *createTree(const char data[], int *index);
    TreeNode *copyTree(TreeNode *node);
    void preOrder(TreeNode *node);
    void inOrder(TreeNode *node);
    void postOrder(TreeNode *node);
    int leafNum(TreeNode *node);
    int height(TreeNode *node);

    void inThreading(TreeNode *node);
    void inOrderTraverse_Thr(TreeNode *node);
    TreeNode *locate(TreeNode *node, const char &);
    TreeNode *inOrderFisrtNode(TreeNode *node);
    TreeNode *inOrderLastNode(TreeNode *node);
};

class HuffmanTree
{
private:
    // 添加必要的数据成员
    // myadd
    class HFNode
    {
    public:
        int left, right;
        // -1表示无父节点
        int parent;
        int weight;
        string code;
    } *HFT;
    int num;

public:
    HuffmanTree(const int &, const int[]); // 构造函数
    ~HuffmanTree();                        // 析构函数

    void printHuffmanCodes();

    // add
    void selectMin(HFNode *hft, int n, int &s1, int &s2);
    void initleaves(int n, const int *data);
    void showHFT(int n);
    // Recursive function to generate Huffman codes
    void generateCodes(int idx, string code);
};